/*
 * @lc app=leetcode id=473 lang=cpp
 *
 * [473] Matchsticks to Square
 */

// @lc code=start
class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        long s = 0;
        for (auto m : matchsticks ) {
            s += m;
        }
        if (s % 4 != 0) {
            return false;
        }
        int n = s / 4;
        int m = 0;
        int mask  = 0;
        for (int i = 0; i < 4; ++i) {
            if (!Solve(matchsticks, n, 0,0, mask)) {
                return false;
            }
        }
        return true;

    }
  bool Solve(vector<int> &matchsticks, int target, int s, int idx, int &mask) {
  if (target == s) {
    return true;
  }
  while ((mask >> idx) & 1) {
    idx++;
  }
  if (idx >= matchsticks.size()) {
    return false;
  }

  if (Solve(matchsticks, target, s + matchsticks[idx], idx + 1, mask)) {
    mask |= 1 << idx;
    return true;
  } else if (Solve(matchsticks, target, s, idx + 1, mask)) {
    return true;
  }

  return false;
}

   
};
// @lc code=end

